1. Field of the Invention
The present invention relates to CRC (Cyclic Redundancy Check) generation in general and in particular to CRC generation as applies to ATM technology.
2. Prior Art
The description which follows presupposes knowledge of data communications networks, protocols, and devices (such as routers, switches, etc.) used to transport data within said communications networks.
One of the well known protocols used to shuttle data in communications networks is Asynchronous Transfer Mode (ATM). In ATM, the data is packaged in ATM cells by source network devices and transported on ATM links to network destination devices.
In the recommendation 1.363, ITU (International Telecommunications Union) has defined 4 ATM adaptation layers (AAL). The goal of AAL is to provide useful services to application programs and to shield them from the burden of splitting the data up into at the source and reassembling at the destination. AAL1 is the protocol for transmitting real-time constant bit rate connection-oriented traffic such as audio and video. However, for compressed audio or video, the rates can vary strongly over time. AAL2 has been defined in 1.363.2 by ITU for handling such type of traffic. This invention concerns itself about AAL2. The ATM cell in AAL2 format can contain multiple full or partial CPS (Common Part Sublayer) packets. The CPS packet header consists of the following fields: channel identifier (CID), a length code (LI), a user to user information (UUI) and a cyclic redundant code (CRC). The lengths of these fields are as follows: CID is 8 bits long, LI is 6 bits long, UUI is 5 bits long and CRC is 5 bits long. Thus, the length of the CPS packet header is 24 bits or 3 bytes long. The five bit CRC protects the fields CID, LI and UUI.
A straightforward and brute force way of generating the CRC would be to use standard CRC algorithms to generate the CRC based upon all 2.sup.M possible values to be protected where M represents number of bits in the fields that need protection. For the CPS Hdr M=19, therefore, the CRC table would be rather large requiring 2.sup.19 entries. A CRC table with 219 entries would require a large amount of storage.
In some machines, storage spaces are limited. Therefore, this size storage is not available for storing CRC tables. Even in machines where storage space is available, only high speed memories could be used. High speed memories are necessary in order to meet performance requirements of most systems. The high speed memories suitable for this type of usage are very expensive and would increase the overall cost of system. If one were to use low performance memories, which are relatively inexpensive, the lookup time to access low performance memories is usually long and would adversely affect system throughput.
In either case, the options available are not acceptable. Therefore, there is a need to provide CRC generation in which the CRC table requires minimum amount of storage.